package mo.offer_special;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class L063 {

    public String replaceWords(List<String> dictionary, String sentence) {
        Trie trie = new Trie();
        for (String word : dictionary) {
            Trie current = trie;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                current.children.putIfAbsent(c, new Trie());
                current = current.children.get(c);
            }
            current.children.put('#', new Trie());
        }
        String[] words = sentence.split(" ");
        for (int i = 0; i < words.length; i++) {
            words[i] = findRoot(words[i], trie);
        }
        return String.join(" ", words);
    }

    private String findRoot(String word, Trie trie) {
        StringBuilder builder = new StringBuilder();
        Trie cur = trie;
        for (char c : word.toCharArray()) {
            if (cur.children.containsKey('#')) {
                return builder.toString();
            }
            if (!cur.children.containsKey(c)) {
                return word;
            }
            builder.append(c);
            cur = cur.children.get(c);
        }
        return builder.toString();
    }


    private static class Trie {
        public Map<Character, Trie> children;

        public Trie() {
            children = new HashMap<>();
        }
    }
}
